package 力扣.中等;

import java.util.*;

/*
* 给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

 

示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
 
*
* 思路：主要使用哈希表 先减最少的在减次少的

*/
public class 不同整数中的最少数目 {
    public static void main(String[] args) {
        int[] arr={4,3,1,1,3,3,2};
        int k=3;
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<arr.length;i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }


      ArrayList<Integer> list=new ArrayList<>();
       for (int c:map.values()){
           list.add(c);
       }

        list.sort(Comparator.naturalOrder());

       int result=list.size();
//       for(int i=0;i<list.size();i++){
//           if(k<=0){
//               break;
//           }
//           if(list.get(i)<=k){
//               k-=list.get(i);
//               result--;
//           }
//           else break;
//       }
        int i=0;
        while(k>0){
            if(list.get(i)<=k){
                k-=list.get(i);
                result--;
                i++;
            }else {
                break;
            };
        }



        System.out.println(result);
    }
}
